import java.util.List;

public class Test {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode min = list1.val < list2.val ? list1 : list2;
        if(min == list1)
            min.next = mergeTwoLists(list1.next, list2);
        else
            min.next = mergeTwoLists(list1, list2.next);
        return min;
    }

    public void move(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if(n == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }
        move(A, C, B, n - 1);
        C.add(A.remove(A.size() - 1));
        move(B, A, C, n - 1);
    }
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        move(A, B, C, n);
    }

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode tmp = head.next;
        head.next = null;
        ListNode newNode = reverseList(tmp);
        newNode.next = head;

        return newNode;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode head1 = new ListNode(2);
        ListNode head2 = new ListNode(3);
        head.next = head1;
        head1.next = head2;
        Test test = new Test();
        ListNode h = test.reverseList(head);
        System.out.println();
    }

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    class Solution {
        public double myPow(double x, int n) {
            return n < 0 ? 1 / pow(x, -(long)n) : pow(x, n);
        }

        double pow(double x, long n) {
            if(n == 0) return 1;
            if(n == 1) return x;
            double y = pow(x, n / 2);
            return n % 2 == 0 ? y * y : y * y * x;
        }
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
